Algorithms are increasingly deployed in settings where the individuals or firms interacting with them behave strategically. In this talk, I will discuss two problems in which this strategic behavior changes the learning problem and the outcomes that can be guaranteed.
First, I will consider strategic classification, where agents manipulate their features, at a cost, to receive a positive classification from a learner’s classifier, and the learner aims to learn a classifier robust to these strategic manipulations. We study learning objectives with minimax group fairness guarantees in a population consisting of several groups, where each group may have its own cost function. For separable costs and a small number of groups, we give an efficient algorithm for learning an approximately optimal deterministic classifier. For general cost functions, we give oracle-efficient algorithms for learning approximately optimal randomized classifiers when the hypothesis class has finite strategic VC dimension.
I will then turn to algorithmic pricing. Here, firms repeatedly choose prices using online learning algorithms, and we study when regret guarantees are sufficient to rule out algorithmic collusion. We characterize how the regret notion and the structure of the pricing game affect the possibility of supra-competitive prices. In particular, we give conditions under which coarse correlated or correlated equilibria collapse to the unique Nash equilibrium, identify settings in which no external regret alone guarantees competitive prices, and study price correctors that modify algorithmic price recommendations so that expected transaction prices converge to competitive levels while firms cannot gain much by reverting to their original recommendations.